1. Field of the Invention
The present invention relates to a method and an apparatus of free space enumeration for collision avoidance, which have a primary application in the field of motion planning of robot manipulators, to be utilized in obtaining a collision-free path in which a moving object such as a manipulator can move without a collision with surrounding objects. The method and the apparatus can also be utilized beneficially as a space enumerator in designing an optimal arrangement of various apparatuses, including piping in factories, and electronic circuitry.
2. Description of the Background Art
For motion planning of a moving object such as a manipulator, between given initial position and configuration, and given final position and configuration, where a path capable of avoiding collisions with surrounding obstacles is sought, use of a so called configuration space of N-dimension parametrically defined in terms of N-degrees of freedom for the manipulator's position and configuration has been considered effective.
In this type of motion planning, there is a one-to-one correspondence between a point of the configuration space and a unique position and configuration of the manipulator, so that the path of the manipulator capable of avoiding collisions with surrounding obstacles, which can easily be highly complicated in 3-dimensional physical space, can be represented by a simple trajectory of the point of the configuration space through a collision free region of the configuration space called a free space.
An example of such a configuration for a manipulator and obstacles shown in FIG. 1(A) is shown in FIG. 1(B), where a vertical axis represents angles of a third joint of the manipulator, and a horizontal axis represents angle of second joint of the manipulator. The 3-dimensional physical configuration shown in FIG. 1(A) is represented by the configuration space shown in FIG. 1(B) in which those values of the second and the third joint angles that cause collisions between the manipulator and the obstacles are shown as a block of black cells (named as a collision cells in the figure), with the remaining free space surrounding it. Thus, for the manipulator to move from an initial configuration represented by a cell A to a final configuration represented by another cell B without colliding with obstacles, a path must be chosen around the collision cells.
Since the configuration space, in general, is divided up into a multiplicity of small regions called cells, it is necessary to determine which cells belong to the free space. Although, in principle, this can easily be accomplished by performing collision detections between the manipulator and the obstacles, a progressive increase in amounts of information to be dealt with accompanying an increase in dimensionality, limits the extent to which collision detections can be carried out.
For instance, a manipulator with 6 degrees of freedom calls for a 6-dimensional configuration space, and when each of the 6 coordinates is to be divided up (or quantized) into 32 equal parts in order to define cells, the number of cells becomes a sixth power of 32, which makes a practical implementation of complete collision detections for all the cells almost impossible.
Thus, in practice a reduction of an amount of information is indispensable.
One known way of achieving this is by considering only those degrees of freedom having major contribution to the motion in accordance with the functional characteristics of the manipulator, and thereby reducing the dimensionality of the configuration space. For example, when the motion of a manipulator with six degrees of freedom can largely be determined by three of those six degrees of freedom related to the main arm alone, the motion of this manipulator may effectively be described by the 3-dimensional configuration space using only three degrees of freedom related to the main arm. However, this way of reducing the amount of information requires a knowledge of those degrees of freedom having major contributions to the motion, which have to be decided case by case, so that not only the preparation for such motion planning becomes cumbersome, but also the general applicability of this type of motion planning is severely restricted.
Another known way of achieving the reduction of the amount of information is, as discussed by the present applicant in "collision avoidance using free space enumeration method based on Lee's algorithm" in Journal of Robotics Society of Japan, Vol. 5, no. 4, pp. 11-20, 1987, to limit the free space to just a region relevant in obtaining the path. However, in such conventional motion planning, in order to achieve reduction of the amount of information, the path has been determined irrespective of ease in motion, so that dangerous paths such as those which are nearly grazing the obstacle have often been resulted. Furthermore, this manner of reducing the amount of information is based on a method called wavefront expansion, which will be explained in detail below, so that it will be seen that the reduction cannot be sufficient for those cases involving six degrees of freedom.
Likewise, in the application of the free space enumerator to design an optimal arrangement of various apparatuses, piping in factory, or electronic circuitry, for example, practically dangerous spaces such as those in the immediate vicinity of obstacles have often been obtained.
As explained, in conventional methods for motion planning, an enormous amount of information required in performing a complete collision detections cannot be suppressed without sacrificing either the general applicability of the methods or the practicality of the path or the space to be obtained.
Furthermore, there is another problem in the conventional methods for motion planning, concerning the manner of quantizing the coordinates of the configuration space. Namely, when the coordinates of the configuration space are quantized by the same interval throughout, as in the conventional methods, due to the differences in significance with respect to the whole motion possessed by different degree of freedom, the quantization may be unnecessarily fine for some such as a main arm portion and too coarse to obtain a sufficient accuracy for the other such as a finger portion. The unnecessarily fine quantization causes a drastic increase in the amount of information to be dealt with, which, in turn, causes a tremendous elongation of operation time. On the other hand, the insufficient accuracy due to the coarse quantization may cause the overlooking of a small obstacle, such as a thin wire.
In addition, conventional methods for motion planning are associated with yet another problem in determination of the free space cells. Since there are many different types of manipulators, with different degrees of freedom, and also since changes in environmental conditions of the manipulator delicately affect the state of the configuration space, the method of determining the free space must cells in the configuration space be chosen carefully, in order for the method to be effective.
However, it is extremely difficult to select an appropriate method for determining the free space cells, as the state of the configuration space is generally not known. Also, it is impossible to deal with all the information on the configuration space. The choice of an inappropriate method for determining the free space cells results in very inefficient operation and all the inconveniences caused by such operation.